#include <string.h>

#include <iostream>
using std::cout;
using std::endl;

// 合并两段有序数组
void Merge(int arr[], int begin, int middle, int end) {
  int* newarr = new int[end - begin];
  int i = begin, j = middle, idx = 0;
  while (i < middle && j < end) {
    if (arr[i] < arr[j]) {
      newarr[idx++] = arr[i];
      i++;
    } else {
      newarr[idx++] = arr[j];
      j++;
    }
  }
  if (i == middle) {
    memcpy(&newarr[idx], &arr[j], (end - j) * sizeof(int));
  }
  if (j == end) {
    memcpy(&newarr[idx], &arr[i], (middle - i) * sizeof(int));
  }
  memcpy(&arr[begin], &newarr[0], (end - begin) * sizeof(int));
  delete[] newarr;
}
// 递归Merge排序，前开后闭区间[begin,end)
void RecurMergeSort(int arr[], int begin, int end) {
  if (end - begin <= 1) return;
  int middle = (begin + end) / 2;
  RecurMergeSort(arr, begin, middle);
  RecurMergeSort(arr, middle, end);
  Merge(arr, begin, middle, end);
}
// 归并排序。缺点：不是原地排序（空间复杂度O(n)）
void MergeSort(int arr[], int size) { RecurMergeSort(arr, 0, size); }

void Swap(int& a, int& b) {
  int tmp = a;
  a = b;
  b = tmp;
}
// 把数组分区成小区间+中间值+大区间，并返回中值索引
int Partition(int arr[], int first, int last) {
  int split = first;
  for (int i = first; i < last; ++i) {
    if (arr[i] < arr[last]) {
      Swap(arr[i], arr[split]);
      ++split;
    }
  }
  Swap(arr[split], arr[last]);
  return split;
}
// 递归Quick排序，前开后开区间[first,last]
void RecurQuickSort(int arr[], int first, int last) {
  if (first >= last) return;
  int split = Partition(arr, first, last);
  RecurQuickSort(arr, first, split - 1);
  RecurQuickSort(arr, split + 1, last);
}
// 快排。最常用，缺点：不是稳定排序
void QuickSort(int arr[], int size) { RecurQuickSort(arr, 0, size - 1); }

typedef void (*SortFunc)(int arr[], int size);

void Print(int arr[], int size) {
  for (int i = 0; i < size; ++i) {
    cout << arr[i] << ' ';
  }
  cout << endl;
}

void TestSort(SortFunc sort) {
  // int arr[] = {1};
  // int arr[] = {2, 8, 6, 3, 1};
  int arr[] = {6, 2, 5, 8, 3, 10, 2, 3, 30, 11};
  sort(arr, sizeof(arr) / sizeof(int));
  Print(arr, sizeof(arr) / sizeof(int));
}

int main() {
  TestSort(MergeSort);
  TestSort(QuickSort);
}